COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input rwflet
C00004 ENDMK
C⊗;
\input rwflet
\memoto Herb Wilf
\from Bob Floyd
\subject Igarashi and Wood Paper
\body
The paper by Igarashi and Wood contains fairly obvious results.  The two parts
of the definition of $k$-sortedness are equivalent, by interchanging $i$ and
$j$.  The number 0.69428 in the abstract should be 9.69424 \dots; I found both
numbers in under 5 minutes on reading the abstract.  Some of the results, as
well as much deeper results, are to be found in Vaughan Pratt's doctoral
dissertation on Shellsort, and in the section on Shellsort in Knuth, Vol.\ 3.
Theoren 5.3 is more simply shown by observing that on totally ordered input, any 
sorting algorithm must compare each $a↓i$ to $a↓{i + 1}$; if it does not, it
fails on input where $a↓i > a↓{i + 1}$ is the only inversion.  The procedure
ONESORT is equivalent to one in the Shellsort section of Knuth.  I do not
recommend publishing in the Journal of Algorithms.
\endletter
\end